【题解】 陌上花开 CDQ分治 bzoj3262 | Qiuly's blog!

【题解】 陌上花开 CDQ分治 bzoj3262

Posted on | Edited on | In | Comments:

陌上花开，可缓缓归矣 ——吴越王

每日一学语文[滑稽]。

当然这题 $KDT​$ 是可以做的，但是不费，所以用 $CDQ​$ 算了吧。

很显然这道题是 $CDQ$ 三维偏序的板子题(luogu上它本来就是板子题)

$CDQ$ 分治的三维偏序怎么做？

对于其中的第一维，$CDQ$之前直接 $sort$ 排好序，那么这就可以保证对于一个 $i<j$ ，位置 $j$ 的元素一定是对位置 $i$ 的元素做不出贡献的，因为 $x_i <x_j$ 。

然后第二维，进入 $CDQ$ ，很显然当前的区间 $l - r$ 是会分成两个子区间分别做 $CDQ$ 的，那么当两个子区间合并的时候，左子区间是可能会对右子区间做出贡献的，但是右子区间对左子区间做不出任何贡献，原因是我们在之前已经按 $x$ 排好了序，那么显然左子区间的元素的 $x$ 始终小于右子区间的元素的 $x$。

外面排好了第一维，那么我们就在 $CDQ$ 中排第二维，由于我们是分成了两个子区间递归处理，往上面合并的时候，正好可以归并排序。第三位只需要在树状数组中记录一下，然后统计答案的时候调用树状数组的查询，看看比当前元素小的有多少个即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void CDQ(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    CDQ(l,mid);CDQ(mid+1,r);/*分成两个子区间*/
    int i=l,j=mid+1,cnt=l;
    while(i<=mid&&j<=r){/*归并+统计答案*/
        if(v[i].b<=v[j].b)add(v[i].c,size[v[i].id]),hep[cnt++]=v[i++];
        /*左子区间的当前元素可能会有贡献，记录一下*/
        else ans[v[j].id]+=sum(v[j].c),hep[cnt++]=v[j++];
        /*接下来的左子区间的b是比当前的j.b要大的了，没有贡献了*/
        /*因为在子区间中使用了归并，所以两个子区间中b肯定是升序的*/
    }
    while(j<=r)ans[v[j].id]+=sum(v[j].c),hep[cnt++]=v[j++];
    /*将剩下的归并排序完*/
    for(int h=l;h<i;++h)add(v[h].c,-size[v[h].id]);
    /*清除树状数组留下的痕迹*/
    while(i<=mid)hep[cnt++]=v[i++];
    for(int i=l;i<=r;++i)v[i]=hep[i];
    /*更新原数组*/
}

$QvQ$ 就这样了，只是这题需要离散化一下，$Code$ 中的 $size$ 就是元素出现的个数。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

#define ll long long

const int N=1e5+2;
const int K=2e5+2;

int n,k;
struct Node{int a,b,c,id;}v[N],hep[N];
int tre[K],ans[N],num[N],size[N];

inline void add(int x,int v){for(;x<=k;x+=(x&-x))tre[x]+=v;};
inline ll sum(int x){ll res=0;for(;x;x-=(x&-x))res+=tre[x];return res;};

template<typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

bool cmp(Node x,Node y){
    if(x.a!=y.a)return x.a<y.a;
    if(x.b!=y.b)return x.b<y.b;
    return x.c<y.c;
}

void CDQ(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    CDQ(l,mid);CDQ(mid+1,r);
    int i=l,j=mid+1,cnt=l;
    while(i<=mid&&j<=r){
        if(v[i].b<=v[j].b)add(v[i].c,size[v[i].id]),hep[cnt++]=v[i++];
        else ans[v[j].id]+=sum(v[j].c),hep[cnt++]=v[j++];
    }
    while(j<=r)ans[v[j].id]+=sum(v[j].c),hep[cnt++]=v[j++];
    for(int h=l;h<i;++h)add(v[h].c,-size[v[h].id]);
    while(i<=mid)hep[cnt++]=v[i++];
    for(int i=l;i<=r;++i)v[i]=hep[i];
}

int main(){
    IN(n),IN(k);
    for(int i=1;i<=n;++i)
       scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].c);
    std::sort(v+1,v+n+1,cmp);
    int tot=0;
    for(int i=1;i<=n;++i){
    	if(v[i].a!=v[i-1].a||v[i].b!=v[i-1].b||v[i].c!=v[i-1].c)hep[++tot]=v[i];
    	++size[tot];
    }
    for(int i=1;i<=tot;++i)v[i]=hep[i],v[i].id=i;
    CDQ(1,tot);
    for(int i=1;i<=tot;++i)
       num[ans[v[i].id]+size[v[i].id]-1]+=size[v[i].id];
    for(int i=0;i<n;++i)
       printf("%d\n",num[i]);
    return 0;
}

本文标题:【题解】 陌上花开 CDQ分治 bzoj3262

文章作者:Qiuly

发布时间:2019年02月22日 - 00:00

最后更新:2019年03月29日 - 13:52

原始链接:http://qiulyblog.github.io/2019/02/22/[题解]bzoj3262/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。